package com.power.algorithm.sort;

/**
 * @description:
 * @author: jiangnan
 * @time: 2021/5/25 9:40 上午
 */
public class ShellSort {
    private int[] array;

    public ShellSort() {
        array = new int[]{1, 4, 2, 7, 9, 8, 3, 6,5,0};
    }

    public void sort() {
        // 十个元素  第一次增长gap = 5 共五个小数组
        // 第二次 gap =2 共两个数组
        //增量gap并逐步缩小
        for (int gap = array.length / 2; gap > 0; gap /= 2) {
            System.out.println(gap);
            //从第gap 个元素 对此一次插入排序
            for (int i = gap; i < array.length; i++) {
                int j = i;
                while (j - gap >= 0 && array[j] < array[j - gap]) {
                    //swap(array[j], array[j - gap]);
                    int tmp = array[j];
                    array[j] = array[j - gap];
                    array[j - gap] = tmp;
                    j -= gap;

                }
            }
        }
    }

    public void display() {
        System.out.print("元素为::: ");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }

    public static void main(String[] args) {
        ShellSort shellSort = new ShellSort();
        shellSort.sort();
        shellSort.display();
    }
}
